It is normal practice to meter, or regulate, the traffic flows in network units such as switched and routers. The general purpose is to ensure so far as practicable that all the users of a network have fair access. In general, the traffic (i.e. the aggregate of the flows of packets) in a network comprises a variety of different protocols, such as TCP/IP (Transmission Control Protocol/Internet Protocol), UDP (User Datagram Protocol), FTP (file Transfer protocol) and so on. All traffic which flows through a network unit is normally stored in memory temporarily while a lookup is performed to determine the destination (local or remote or both) of the packet and for the completion of other processing which may be necessary or desirable before the packet is forwarded from the unit. Since memories are of finite size the phenomenon of congestion is an ever-present threat. It may arise in a given unit because there is congestion down stream, so that packets cannot be transmitted from the unit from at least some output ports while that downstream congestion persists; or the unit receives at input ports input flows which are greater than the unit can accommodate for more than brief periods.
Some protocols (such as TCP) include congestion control features, but others, such as UDP, do not.
The ultimate remedy for congestion in a unit is for the unit to ‘drop’ i.e. discard packets. However, such a remedy cannot be applied indiscriminately. Some flows may be constituted by packets conforming to a protocol which is adaptive, in the sense that they include two-way communication that enables a sender to determine whether there has been packet loss and cause reduction in the respective data rate. Other protocols do not have this feature. Furthermore, some forms of traffic, though not necessarily occupying a high fraction of the variable bandwidth, are particularly sensitive to packet loss.
A traffic flow may be defined in a variety of different ways. A simply defined flow is characterized by a particular source port or destination port. A flow may be defined by a source port/destination port pair. Fields from different protocol layers may be combined, particularly to identify a TCP flow; a classifier may be a 5-tuple access control list comprising an IPSA (internet protocol source address); an IPDA (internet protocol source address), an ‘application’ source port number; an ‘application’ destination port number and a field identifying a transport protocol, such as TCP. Normally each flow may be defined by a multiplicity of criteria and selected by means of a ‘classification’ or ‘rules’ engine which examines selected part of packets received by the unit for matching against entries in a ‘flow’ database.
Packet metering schemes must therefore take into account the fact that a given flow may contain a mix of packets sent with different protocols; that different flows may require greater or lesser bandwidth than others; that that some flows may be non-adaptive and so on; and need to be capable of variable control, so that rate selected for given flow may be adjusted.
The problem of flow rate metering is acerbated by the multiplicity of different flows that may be defined.
One popular scheme for the metering of flow rates employs ‘token buckets’, usually one such token bucket for each flow. A token bucket is in essence a logical counter which is periodically ‘refreshed’. This means that it receives a number of ‘tokens’ which are conventionally defined as a measure of packet size; for example a token may represent a number of bytes. Normally the bucket has a maximum capacity. For example it may have a capacity for 1000 (1 k) tokens, which may represent 1000 bytes (or some other number depending on the factor of proportionality). Each time a packet belonging to the respective flow is received, the size of the packet (in units of tokens) is compared with the content of the bucket. If the size of the packet is greater than the number of tokens in the bucket, the packet is not allowed to proceed, and would usually be discarded by any suitable mechanism. If the size of the packet is less than the number of tokens in the bucket, the packet is allowed to proceed, and tokens are removed from the bucket, in accordance with the size of the packet.
Token bucket systems for metering a multiplicity of flows have several disadvantages. Some arise because the large number of meters have to be implemented in memory, usually a memory block separate from that which stores the packets.
One such particular disadvantage is the need to refresh the bucket at regular intervals. The operation of refreshing necessarily occupies the bandwidth available for access to the memory. Token bucket systems require two kinds of access; one for refreshing and the other for up-dating, whereby the meter is accessed to determine whether there are sufficient tokens for allowing the passage of a packet. The greater the number of meters, the greater the bandwidth required to refresh them and the lesser the bandwidth available for up-dating them. Although one has a choice whether to refresh a bucket with a greater number of tokens at less frequent intervals or a lesser number of tokens at a greater frequency, in practice the latter, which has a greater impact on the bandwidth, is preferred to reduce the occurrence of bursty traffic.
A second disadvantage is inherent in the nature of a token bucket. The bucket will allow packets to pass through the meter as long as there are sufficient tokens in the bucket. There is no restriction on the rate of removal of tokens from the bucket. Therefore there is no restriction on the flow of packets until the bucket is empty (on the normal assumption that a bucket holds tokens to the equivalent of a multiplicity of packets). When a bucket is empty, and requires repeated replenishment before it is full again, there will be a much reduced flow of packets. The consequent alternation of rates, between bursts and drips, is undesirable for a flow of voice data or other data representing events in real time.
There is therefore a need for a metering scheme that is versatile, in that it can accommodate a large number of possible different flows without excessive usage of memory bandwidth and can accommodate a great range of different rates without the inherent susceptibility to the production of bursts of traffic.